import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution102 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static class Pair{
        TreeNode treeNode;
        int deep;

        public Pair(TreeNode treeNode, int deep) {
            this.treeNode = treeNode;
            this.deep = deep;
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans=new ArrayList<>();
        Queue<Pair> queue=new LinkedList<>();
        if (root!=null){
            queue.offer(new Pair(root,0));
        }
        while (!queue.isEmpty()){
            Pair pair=queue.poll();
            if (ans.size()==pair.deep){
                ans.add(new ArrayList<>());
            }
            ans.get(pair.deep).add(pair.treeNode.val);
            if (pair.treeNode.left!=null){
                queue.offer(new Pair(pair.treeNode.left,pair.deep+1));
            }
            if (pair.treeNode.right!=null){
                queue.offer(new Pair(pair.treeNode.right,pair.deep+1));
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution102().levelOrder(new TreeNode(3,new TreeNode(9),new TreeNode(20,new TreeNode(15),new TreeNode(7)))));
    }
}
